package com.zhengb.algorithmdemo.exam;

/**
 * @author zhengbo
 * @date 2020/2/25
 */
public class ArraySort {

    /**
     * 是否是有序递增数组
     *
     * @param array
     * @return
     */
    private static boolean checkIsOrderlyIncreaseArray(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] >= array[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 合并两个有序的整型
     *
     * @param array1 数组1
     * @param array2 数组2
     * @return 合并后且去重的数组
     */
    public static int[] mergerOrderlyArrays(int[] array1, int[] array2) {
        if (array1.length == 0 && array2.length == 0) {
            return new int[0];
        }
        if (!checkIsOrderlyIncreaseArray(array1) || !checkIsOrderlyIncreaseArray(array2)) {
            throw new IllegalArgumentException("array1 or array2 is not a orderly increase array!!");
        }

        //两个数组总的长度
        int totalLength = array1.length + array2.length;

        //初始化一个临时数组 用于存放合并后的元素
        int[] tempArray = new int[totalLength];

        //array1和array2中重复元素个数
        int repeatCount = 0;

        int i = 0, j = 0, k = 0;

        while (i < array1.length && j < array2.length) {
            if (array1[i] < array2[j]) {
                tempArray[k++] = array1[i++];
            } else if (array1[i] == array2[j]) {
                tempArray[k++] = array1[i++];
                j++;
                repeatCount++;
            } else {
                tempArray[k++] = array2[j++];
            }
        }
        //添加array1剩下的元素
        while (i < array1.length) {
            tempArray[k++] = array1[i++];
        }
        //添加array2剩下的元素
        while (j < array2.length) {
            tempArray[k++] = array2[j++];
        }
        //合并后数组长度=总长度-重复元素数量
        int resultArrayLength = totalLength - repeatCount;
        int[] resultArray = new int[resultArrayLength];

        //拷贝临时数组元素至结果数组
        System.arraycopy(tempArray, 0, resultArray, 0, resultArrayLength);

        return resultArray;
    }
}
